package com.explorati.LeetCode093.restoreIpAddresses;

import java.util.ArrayList;
import java.util.List;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 21:15 2020/9/23 0023
 * @ Description ：
 */
public class Solution {

    List<String> res = new ArrayList<String>();
    /**
     * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
     */
    public List<String> restoreIpAddresses(String s) {
        //每个整数为 0-255之间，一共四个
        findIpAddresses(s, 0, "");
        return res;
    }

    /**
     *
     * @param s         剩余的字符
     * @param index     当前位置的字符
     * @param preStr    前面组装的字符
     */
    private void findIpAddresses(String s, int index, String preStr){
        //如果都遍历完成，将符合条件的结果装到res中
        if(index == 4) {
            res.add(preStr);
            return;
        }
        //查看每次遍历的位数是否符合规则，如第一个数 需要4<= s <= 12，第二个数 需要3<= s <= 9，否则构成不了ip地址(长度不符合)
        if(s.length() < (4 - index) || s.length() > (4 - index) * 3) {
            return ;
        }

        /*
         * 如果是前三位的话，限制条件有:
         * 1. 如果第一位为0，那么只能为0
         * 2. 不能大于255
         *
         * 如果是第4位，限制条件：
         * 1. 同上
         * 2. 直接接上所有字符串，不需遍历再递归
         */
        String curStr = null;
        //如果是前3位
        if(index < 3){
            //如果第一位为0，只能为0
            if(s.charAt(0) == '0') {
                curStr = s.substring(0,1);
            }else if(s.length() < 3) {
                //第一位不为0，且s的长度小于3，那么需要考虑后面剩余的位数，至少需多出剩余位数的个数
                //假如当前位为第3位(index为2)，一共剩余2位(s.length)，那么第四位至少需要一位，所以第3位只能取到1位，通用公式为s.length() - (4 - index - 1)
                curStr = s.substring(0, s.length() - (4 - index - 1));
            }else if(Integer.parseInt(s.substring(0, 3)) > 255){
                curStr = s.substring(0, 2);
            }else {
                curStr = s.substring(0, 3);
            }
            for(int i = 0; i < curStr.length(); i ++) {
                String curLetter;
                if(index == 0) {
                    curLetter = curStr.substring(0, i + 1);
                }else {
                    curLetter = "." + curStr.substring(0, i + 1);
                }

//                if(i + 1 >= s.length()) {
//                    return;
//                }
                findIpAddresses(s.substring(i + 1), index + 1,  preStr + curLetter);
            }
        }
        if(index == 3){
            //最后一位数
            if(s.charAt(0) == '0' && s.length() > 1) {
                return;
            }
            if(Integer.parseInt(s) > 255) {
                return;
            }
            findIpAddresses(s, index + 1, preStr + "." + s);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "1111";
        List<String> res = solution.restoreIpAddresses(s);
        res.forEach(row -> System.out.println(row.toString()));
    }

}
